package org.zdw.data.structure.sort;

import org.zdw.data.structure.util.CreateArray;

/**
 * 归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。
 * 归并的含义是将两个或两个以上的有序表合并成一个新的有序表。
 * 归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。
 * 这里仅对内排序的两路归并方法进行讨论。
 * 分而治之(divide - conquer);每个递归过程涉及三个步骤
 *第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
 *第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
 *第三, 合并: 合并两个排好序的子序列,生成排序结果.
 */
public class MerginSort {

    public static void sort(int[] array){
        if(array.length > 0){
            sort(array,0,array.length-1);
        }
    }

    public static void sort(int[] data, int left, int right) {
        if(left<right){
            //找出中间索引
            int center=(left+right)/2;
            //对左边数组进行递归
            sort(data,left,center);
            //对右边数组进行递归
            sort(data,center+1,right);
            //合并
            merge(data,left,center,right);
        }

    }

    public static void merge(int[] data, int left, int center, int right) {
        int [] tmpArr=new int[data.length];
        int mid=center+1;
        //third记录中间数组的索引
        int third=left;
        int tmp=left;
        while(left<=center&&mid<=right){
            //从两个数组中取出最小的放入中间数组
            if(data[left]<=data[mid]){
                tmpArr[third++]=data[left++];
            }else{
                tmpArr[third++]=data[mid++];
            }

        }

        //剩余部分依次放入中间数组
        while(mid<=right){
            tmpArr[third++]=data[mid++];
        }

        while(left<=center){
            tmpArr[third++]=data[left++];
        }

        //将中间数组中的内容复制回原数组
        while(tmp<=right){
            data[tmp]=tmpArr[tmp++];
        }

        CreateArray.printArray(tmpArr);
    }
}
